Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1

Input: "2-1-1".

  1. ((2-1)-1) = 0
  2. (2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

  1. (2*(3-(4*5))) = -34
  2. ((2*3)-(4*5)) = -14
  3. ((2*(3-4))*5) = -10
  4. (2*((3-4)*5)) = -10
  5. (((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

Solution:

  1. public class Solution {
  2.   public List<Integer> diffWaysToCompute(String input) {
  3.     List<Integer> res = new ArrayList<Integer>();
  5.     for (int i = 1; i < input.length(); i++) {
  6.       char c = input.charAt(i);
  8.       if (c == '+' || c == '-' || c == '*') {
  9.         String s1 = input.substring(0, i);
  10.         String s2 = input.substring(i + 1);
  12.         List<Integer> l1 = diffWaysToCompute(s1);
  13.         List<Integer> l2 = diffWaysToCompute(s2);
  15.         for (Integer n1 : l1) {
  16.           for (Integer n2 : l2) {
  17.             switch (c) {
  18.               case '+': res.add(n1 + n2); break;
  19.               case '-': res.add(n1 - n2); break;
  20.               case '*': res.add(n1 * n2); break;
  21.             }
  22.           }
  23.         }
  24.       }
  25.     }
  27.     if (res.size() == 0) {
  28.       res.add(Integer.valueOf(input));
  29.     }
  31.     return res;
  32.   }
  33. }